1. Field of Invention
The invention relates to a method for uploading data, and in particular to a method for allocating transmission bandwidths of a network.
2. Related Art
For a long time now bandwidth allocation has been an important subject in designing a network system. Taking a passive optical network (PON) as an example, multiple optical network units (ONU) are disposed at a corresponding number of offices or houses, using passive devices to couple to a single optical line terminal (OLT). In other words, an optical line terminal located at one end connects to an optical couple device, which is near a terminal (client side), by an optical fiber, and then goes to the optical network unit. Here, data can be transmitted to the optical network unit by the broadcasting of the optical line terminal, which is called a downloading process. On the other hand, as shown in FIG. 1, an uploading process means an optical network unit performs a time division multiplexing (TDM) process to transmit the data to the optical line terminal. While uploading data, the uploading bandwidth is shared by all optical network units, therefore bandwidth allocation directly affects transmission speed when uploading data and the efficiency of the bandwidth. However, the current method of allocating bandwidth cannot provide the required properties such as low transmission delay, high bandwidth efficiency and fairness of bandwidth allocation.
Traditionally, each optical network unit is allocated at the same portion of a whole bandwidth (i.e. in one time division multiplexing channel) and the transmissions of those optical network units are synchronized to prevent collision (e.g. two or more optical network units have partially overlapping transmission). For instance, in the related art, N pieces of optical network units are separately assigned to a time slot and adapted to it. Every optical network unit can transmit any number of data package as shown in FIG. 2. Here, if some package cannot complete the transmission in the current time slot, this package must be retained and wait until the next time slot to transmit. Although there will be no collisions and package separations occurring in this method, this time slot allocation method with circulation fixing cannot handle a situation like bursting net flow.
Therefore, a dynamic bandwidth allocating method has been provided. This method is able to reduce the corresponding size of time slots when no data package is transmitted, and give the remainder of the bandwidth to other optical network units to use. However, according to this method, in order to receive time slot assignments precisely, the optical line terminal must acknowledge how many bits of data packages are waiting in every optical network unit before the assignment. Here, every optical network unit transmits a specific message to inform the optical network terminal how many bits of data packages are sent before the data transmission. Then the optical line terminal is able to estimate and allocate the bandwidth to the optical network unit which is going to transmit a data package, inform the optical network unit about the transmittable bandwidth, and start data package transmission. During the uploading process, the optical line terminal monitors the transmission by the optical network unit in a proper order for arranging the transmission timing of the next optical network unit, so that it can receive the next transmitting data package from the next optical network unit after the last data transmission.
In the dynamic bandwidth allocation structure, lots of algorithms for the dynamic bandwidth allocation are provided. For example, U.S. patent application 20030048805 A1 provides an algorithm for the dynamic bandwidth allocation, shown in FIG. 3. In this figure, this method sets up an assured bandwidth B_minj for every optical network unit, where j is the number of the terminals with the requested bandwidth, or the number of optical network units with the requested bandwidth. In other words, if a usable bandwidth of the nth cycle is B_ref, the usable bandwidth of the optical network unit in the nth cycle will be allocated based on the proportion of the assured bandwidth B_minj. After that, in the nth cycle, an ideal usable bandwidth B_idealj,n for every optical network unit with requested bandwidth can be obtained by the allocated usable bandwidth subtracting the compensation value B_addj,n−1. Next, bandwidth allocation proceeds. When the ideal bandwidth B_idealj,n of the optical network unit is larger than 0, the allocated transmittable bandwidth B_tempj,n of the optical network unit is the bandwidth Qj,n requested; otherwise the allocated transmittable bandwidth B_tempj,n is 0. After the bandwidth allocation is completed and the compensation value B_addj,n is recalculated, the allocation of the uploading bandwidth for the optical network unit is completed.
The compensation value is the sum of overspent bandwidths accumulated before this cycle of each optical network unit. When the compensation value is larger than 0, there is an overspent bandwidth before this cycle. On the other hand, when the compensation value is smaller than 0, there is a remaining bandwidth before this cycle.
Under this structure, although a fairness of bandwidth allocation can be obtained, problems remain. If the optical network unit doesn't use many bandwidths for a long time, the remaining bandwidth will be largely accumulated. And when this optical network unit suddenly produces a large amount of bandwidth requests, a large amount of bandwidth will be exhausted, leading to a longer transmitting delay to other optical network units. On the other hand, if the optical network unit maintains a large amount of bandwidth requests for a long time, a usable ideal bandwidth can hardly be stable, leading to a large jittering of the transmitting delay.
In addition, other related documents show another dynamic bandwidth allocation algorithm. See Chadi M. Assi, Yinghua Ye, Sudhir Dixit, and Mohamed A. Ali, “Dynamic Bandwidth Allocation for Quality-of-Service Over Ethernet PONs, “IEEE Journal on Selected Areas in Communications, Vol. 21, No. 9, November 2003, pp. 1467-1477. This method allocated the usable bandwidth to each optical network unit based on the assured bandwidth and the requested bandwidth in this cycle, and then allocated the overspent bandwidth (i.e. the remaining usable bandwidth) based on the requested bandwidth, which is represented by the following formula.
                              B_grant          j                =                  {                                                                                          R                    j                                    ,                                                                                                  if                    ⁢                                                                                  ⁢                                          R                      j                                                        ≤                                      B_min                    j                                                                                                                                                                  B_min                      j                                        +                                          B_excess                      j                                                        ,                                                                                                  if                    ⁢                                                                                  ⁢                                          R                      j                                                        >                                      B_min                    j                                                                                                          (        1        )                                          B_min          j                =                                                            (                                                      T                    cycle                                    -                                      N                    ×                                          T                      g                                                                      )                            ×              r                        8                    ×                      w            j                                              (        2        )                                          B_excess          j                =                              B_left            ×                          R              j                                                          ∑                              k                ∈                K                                      ⁢                          R              k                                                          (        3        )            
Here, the formula (1) is the basic method for the major bandwidth allocation, where Rj is the requested bandwidth for every optical network unit; B_minj is the assured bandwidth for every optical network unit; B_excessj is the excess bandwidth reallocated to the optical network unit with the remaining bandwidth; and B_grantj is the bandwidth (i.e. transmittable bandwidth) the optical network unit actually received. According to the formula (1), when the requested bandwidth is smaller or equal to the assured bandwidth, the optical network unit receives the bandwidth requested; otherwise the optical network unit receives the excess bandwidth in addition to the assured bandwidth. Here, the assured bandwidth can be calculated by the formula (2), where Tcycle is the cycle time; N is the number of the optical network units; Tg is the switching time of the optical network unit; r is the transmitting rate; and wj is the assured bandwidth weight value of the optical network unit, which is determined by the costumer contract. Furthermore, the excess bandwidth can be calculated by the formula (3), where B_left is the remaining bandwidth of the usable bandwidth in this cycle after the allocation of the assured bandwidth, and K is a class of the massive loading (i.e. the requested bandwidth is larger than the assured bandwidth) optical network units, which is represented by K={Rj>B_minj}.
Although this framework can use the remaining bandwidth effectively, it allocates the remaining bandwidth based on the proportion of the requested bandwidth of the optical network unit, which is not fair. So costumers who only buy less bandwidth may have large amounts of transmittable bandwidth to use just because they request it.
Therefore, another method was provided to use the flow prediction process to previously allocate the spare bandwidth in order to reduce the holding time of the high priority data, which is accomplished by the following formulas.Rj=(Hj+E_waitj(n))+Mj+Lj  (4)E_waitj(n)=A_waitj(n−1)  (5)
According to the formula (4), the requested bandwidth of the optical network unit consists of requested band widths with high (Hj), medium (Mj), and low, (Lj) priorities, where a flow prediction value (E_waitj(n)) is added to the high priority part and n is the number of the cycles. From the formula (5), A_waitj(n−1) represents the amount of data actually reaching high priority in the holding period of the n−1th cycle. This shows that the flow prediction value (E_waitj(n)) is the requested bandwidths for high priority reaching the holding period of the last cycle.
However, although this process can reduce the averaged transmission delay of the high priority data, it increases the average transmission delay of other priority data and the inaccuracy of the flow prediction reduces the efficiency of the bandwidth.
Thus, how to effectively provide low delay transmission, high bandwidth efficiency and fairness of bandwidth allocation becomes very important research in this bandwidth allocation field.